package code2201_2300.code70_80;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 给定一个链表的 头节点 head ，请判断其是否为回文链表。
 *
 * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
 *
 * 输入: head = [1,2,3,3,2,1]
 * 输出: true
 *
 * 输入: head = [1,2]
 * 输出: false
 */
public class _2276_Offer27_isPalindrome {


    /**
     * 效率较低
     * 执行用时：     * 7 ms     * , 在所有 Java 提交中击败了     * 49.89%     * 的用户
     * 内存消耗：     * 61.1 MB     * , 在所有 Java 提交中击败了     * 5.08%     * 的用户
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)return true;
        int length = 0;
        ListNode node = head;
        while (node!=null){
            ++length;
            node = node.next;
        }
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        node = head;
        for (int i = 0; i < length / 2; i++) {
            stack.addLast(node.val);
            node = node.next;
        }
        if(length%2==1)node = node.next;
        while (node != null){
            if(node.val == stack.pollLast()){
                node = node.next;
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        System.out.println(isPalindrome(node));
    }


    /**
     * 题解方法 快慢指针！
     *
     * 执行用时：     * 6 ms     * , 在所有 Java 提交中击败了     * 64.48%     * 的用户
     * 内存消耗：     * 48.5 MB     * , 在所有 Java 提交中击败了     * 52.88%     * 的用户
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     *
     * 自己怎么没想到快慢指针！
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 48.5 MB     * , 在所有 Java 提交中击败了     * 54.19%     * 的用户
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
        //1.从中间截断，前长后短
        ListNode fast=head;
        ListNode slow=head;
        while(slow.next!=null&&fast.next!=null){
            fast=fast.next;
            if(fast.next!=null)fast=fast.next;
            else break;
            slow=slow.next;
        }
        //2.反转后面的列表
        ListNode node=slow.next;
        ListNode store=null;
        ListNode next=null;
        while (node!=null){
            next=node.next;
            node.next=store;
            store=node;
            node=next;
        }
        //3.比较 后面的字符串较短
        while (store!=null){
            if(store.val!=head.val)return false;
            store=store.next;
            head=head.next;
        }
        return true;
    }

}
